package oj;
import java.util.Set;
import java.util.HashSet;

//相交链表
public class Num160 {
//    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//        Set<ListNode> visited = new HashSet<ListNode>();
//        ListNode temp = headA;
//        while (temp != null) {
//            visited.add(temp);
//            temp = temp.next;
//        }
//        temp = headB;
//        while (temp != null) {
//            if (visited.contains(temp)) {
//                return temp;
//            }
//            temp = temp.next;
//        }
//        return null;
//    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pA = headA;
        ListNode pB = headB;
        while(pA != pB){
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        int lenA = GetListLen(headA);
        int lenB = GetListLen(headB);
        if(lenA == 0 || lenB == 0){
            return null;
        }
        ListNode longHead = new ListNode();
        ListNode shortHead = new ListNode();

        int step = 0;
        if(lenA > lenB){
            longHead = headA;
            shortHead = headB;
            step = lenA - lenB;
        }else {
            longHead = headB;
            shortHead = headA;
            step = lenB - lenA;
        }
        while (step-- != 0){
            longHead = longHead.next;
        }
        while (shortHead != null && longHead != null){
            if(shortHead == longHead){
                return  shortHead;
            }
            shortHead = shortHead.next;
            longHead = longHead.next;
        }
        return null;
    }

    int GetListLen(ListNode head)
    {
        int len = 0;
        while(head != null)
        {
            len++;
            head = head.next;
        }
        return len;
    }

}
